Instruction set architectures (ISA) specify how central processing units (CPU) execute programs. The programs include instructions stored in memory. Instructions are typically simple, primitive operations such as add, branch on condition, load from memory, and store to memory.
To provide for software compatibility with legacy computer systems, modern CPUs should adhere to the ISA with minimal defects. To achieve this goal, computer designers could verify the correct behavior of each kind of instruction in isolation. However, this may not be sufficient because, in an effort to improve performance, modern CPUs may overlap the execution of numerous instructions. In this environment, some defects may be exposed only when specific combinations of instructions are executed in sequence. Thus, the designer may desire to test every combination or sequence of instructions. However, modern CPUs typically execute over 100 instructions, each of which can include numerous options. Mechanically enumerating all of these possible instructions sequences may not feasible. Even if all possible instruction sequences were enumerated, the designer's test regime may be insufficient because many defects require more than just a specific sequence of instructions. In particular, additional events, such as operand data patterns, memory address collisions between instructions, the state of CPU structures such as cache memories, and stimulus received by the CPU can pre condition defects.
One of the most important tools used by a CPU designer to address these challenges is a Random Code Generator (RCG). The RCG creates a random software program that is used during the CPU design and prototype verification process to generate billions of random instructions to test the CPU.
The RCG creates the initial state of the CPU for each random software program. The initial state includes instructions in memory, and data used by these instructions. The data can be located in memory or CPU structures like registers and caches. An expected final state is also required to check the actual final state created by running the random program on the CPU. The expected final state can be created by the RCG. Alternatively, the expected final state can be obtained by running the random software program on a separate CPU reference emulator.
The RCG maintains two models of the state of the CPU registers: the initial state and the current state. The CPU registers and memory are collectively referred to as data locations. In operation, a typical RCG operation creates random values for all data locations and stores them in the initial and current states. The RCG then loops until a desired program length is achieved. A typical random software program length may be 100 instructions or more. A program counter is used to track the instructions in the random software program. If the program counter points to an uninitialized instruction memory, the RCG generates a random instruction and stores the initial and current states. Next, the instruction pointed to by the program counter is emulated, updating the current state. The program counters then increments and the next instruction is examined.
This method may work in some cases, but is often insufficient for generating high quality random software programs in many other cases. Examples of these cases include: 1) when it is desirable for addresses used by load/store instructions to contend for the same cache locations; 2) when it is desirable to avoid instruction operands that result in an excessive number of traps; 3) when it is desirable to select branch target addresses that cause different parts of the program to contend for the same cache locations; and 4) when it is desirable to avoid instruction operands that the ISA specifies are illegal or that may cause unpredictable results.
In current systems, the RCG can set aside a sub set of the registers for specific use such as memory addressing for load and store instructions. Instead of being given random values, these registers can be given desirable values. But these registers cannot be changed by the random software program because they would be overwritten with random values. This makes it impossible for the random software program to test use of these registers after an earlier modification of the registers. This situation provides unacceptable coverage holes.
In other current systems, when the RCG first selects the operands registers for an instruction, and those registers hold values that are undesirable, the RCG may repeat the selection one or more times until more suitable registers are found. The problem is that the requirements for a register value to be desirable are often very specific. Further, no desirable registers may be available. If a desirable register is available, this approach would tend to select the desirable register a disproportionate number of times, thereby reducing the quality of the test coverage.